package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  //排序
        List<List<Integer>> re = new ArrayList<List<Integer>>();

        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < nums.length; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int twoSum = nums[i] + nums[j];
                int oppositeValue = findOppositeValue(twoSum, j + 1, nums.length - 1, j, nums);
                if (oppositeValue > Integer.MIN_VALUE) {
                    List<Integer> tempRe = new ArrayList<>();
                    tempRe.add(nums[i]);
                    tempRe.add(nums[j]);
                    tempRe.add(oppositeValue);
                    re.add(tempRe);
                }
            }
        }

        return re;
    }

    public int findOppositeValue(int value, int start, int end, int ignoreIndex, int[] nums) {
        if (end < start) {
            return Integer.MIN_VALUE;
        }

        int mid = (end + start) / 2;
        if (ignoreIndex == mid) {
            return Integer.MIN_VALUE;
        }

        int twoSum = value + nums[mid];
        if (0 == twoSum) {
            return nums[mid];
        }
        if (0 < twoSum) {
            return findOppositeValue(value, start, mid - 1, ignoreIndex, nums);
        }

        return findOppositeValue(value, mid + 1, end, ignoreIndex, nums);
    }

    public static void main(String[] args) {
        LC15 an = new LC15();
        int[] nums = {0, 0, 0, 0};
//        int[] nums = {-1, 0, 1, 2, -1, -4, 19, 21};
//        Arrays.sort(nums);  //排序
        System.out.println(an.threeSum(nums));
    }
}
